package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481?tpId=117&&tqId=37796&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking">
 * NC91 最长递增子序列</a>
 *
 * @author or2
 * @Description 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
 * @create 2021年09月01日 时间: 18:07
 */
public class LISSolution {
    /**
     * retrun the longest increasing subsequence
     *
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS(int[] arr) {
//        分配内存
        int[] auxiliary = new int[arr.length];
        int[] ends = new int[arr.length];
//        初始化变量
        auxiliary[0] = 1;
        ends[0] = arr[0];
        int endsLength = 1;
//        记录答案, arr数组中的下标
        int maxIndex = 0;
//        开始算法
        for (int i = 1; i < arr.length; i++) {
            int search = binarySearch(ends, endsLength, arr[i]);
            switch (search) {
//                此数在ends中最大
                case -2:
                    ends[endsLength] = arr[i];
                    endsLength++;
                    auxiliary[i] = endsLength;
                    maxIndex = i;
                    break;
                case -1:
                    throw new RuntimeException("二分查找未找到该数位置。");
//                更新ends数组
                default:
                    ends[search] = arr[i];
                    auxiliary[i] = search + 1;
//                    若更新的是最后一位, 同时更新答案下标
                    if (endsLength == search + 1) {
                        maxIndex = i;
                    }
                    break;
            }
        }
//        整理答案
        int weigth = auxiliary[maxIndex];
        int[] list = new int[weigth];
        for (int index = maxIndex; index >= 0; index--) {
            if (auxiliary[index] == weigth) {
                list[weigth - 1] = arr[index];
                weigth--;
            }
            if (weigth < 0) {
                break;
            }
        }

        return list;
    }

    /**
     * 对整型数组进行二分查找, 找比 value大的最小值
     *
     * @param arr 被查找的数组
     * @param length 该数组的长度
     * @param value 被查找的值
     * @return 在该数组中的下标
     */
    public int binarySearch(int[] arr, int length, int value) {
//        条件初始化 - [) 查找区间形式
        int lIndex = 0;
        int rIndex = length;
        int mid;
//        没有比 value 大的值, 返回-2
        if (arr[length - 1] < value) {
            return -2;
        }
//        都比value大, 返回0
        if (arr[0] > value) {
            return 0;
        } else if (arr[1] > value) {
            return 1;
        }

//        开始循环查找 - [)
        while (lIndex < rIndex) {
            mid = (rIndex - lIndex >> 1) + lIndex;

//            正式二分查找, 大于 value 的最小的数(可以等于)
            if (arr[mid] >= value && arr[mid - 1] < value) {
                return mid;
            } else {
                if (arr[mid] > value) {
//                [lIndex, rIndex)区间内查找
                    rIndex = mid;
                } else {
                    lIndex = mid + 1;
                }
            }
        }
        return -1;
    }
}
